package com.fmm.medium;

public class MazeConnectivity {

    /**
     * @param maze 代表迷宫，0代表可走，1代表不可走
     * @param startX 起点X坐标
     * @param startY 起点Y坐标
     * @param endX 终点X坐标
     * @param endY 终点Y坐标
     * @return 起点到终点是否连通
     * */
    public static boolean mazeConnectivity(int[][] maze, int startX, int startY, int endX, int endY) {
        // 判断起点和终点是否在迷宫内
        if (startX < 0 || startX >= maze.length || startY < 0 || startY >= maze[0].length) {
            return false;
        }
        // 如果起点和终点相遇，返回 true
        if (startX == endX && startY == endY) {
            return true;
        }
        // 起点不能是 1，如果是 1 表示已经碰到墙壁
        if (maze[startX][startY] == 1) {
            return false;
        }
        // 如果起点是0，则将起点标记为1，表示已经走过
        maze[startX][startY] = 1;
        // 递归判断起点的相邻位置是否连通，有一个能连通就是可以连通
        return mazeConnectivity(maze, startX + 1, startY, endX, endY)
                || mazeConnectivity(maze, startX - 1, startY, endX, endY)
                || mazeConnectivity(maze, startX, startY + 1, endX, endY)
                || mazeConnectivity(maze, startX, startY - 1, endX, endY);
    }

    public static void main(String[] args) {
        int[][] maze = {
                {0, 0, 0, 0},
                {0, 1, 0, 1},
                {0, 0, 1, 0},
                {0, 0, 1, 0}};
        int startX = 2;
        int startY = 3;
        int endX = 3;
        int endY = 3;
        System.out.println(mazeConnectivity(maze, startX, startY, endX, endY));
    }
}
